package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname DecodeWays
 * @Description Leetcode 91 解码方法 动态规划  中等难度 自己思路
 * @Date 2021/12/29 16:38
 * @Version 1.0
 */
public class DecodeWays {

    /**
     * 1.base case
     * 2.状态方程
     *
     * @param s
     * @return
     */
    public int numDecodings(String s) {

        int len = s.length();
        //1.动态方程组的含义:
        int[] dp = new int[len + 1];
        //2.base case
        dp[0] = 1;

        for (int i = 1; i <= len; i++) {
            //当前字符不为0
            if (s.charAt(i - 1) - '0' > 0) {
                dp[i] = dp[i] + dp[i - 1];
            }
            //当前字符不为
            if (i > 1 && s.charAt(i - 2) - '0' > 0) {
                int num = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
                if (num <= 26) {
                    dp[i] = dp[i] + dp[i - 2];
                }
            }

        }

        return dp[len];
    }

    public static void main(String[] args) {
        DecodeWays decodeWays = new DecodeWays();
        int i = decodeWays.numDecodings("06");
        System.out.println(i);
    }
}
